Network protocols are standardized methods of moving information, typically in the form of packets, from one node (the source) to another (the destination). There are several different classes of service that can be provided by a network protocol. One such class, known as “best effort”, defines the scenario in which information is sent by the source with no guarantee that it is successfully received by the destination. A second class of service also exists, whereby information sent by the source is guaranteed to arrive at the destination. There are a number of methods by which this can be implemented. The most common method is through the use of acknowledgements (also known as ACKs), which are transmissions sent by the destination back to the source indicating that a previous transmission from the source has been successfully received. In the case where an acknowledgement has not been received by the source, or a negative acknowledgement (also known as a NAK) has been received, the source will retransmit the unsuccessfully transmitted packet.
In order for the source to be able to retransmit a previously unsuccessful packet, it must save that packet until it receives an acknowledgement that it has been received. In some implementations, the source is not permitted to send any additional packets until the previously sent packet has been acknowledged. This minimizes the amount of previously sent information that the source must retain. However, it imposes a significant performance impact. Before the source can transmit a second packet, it must wait for the packet to be transmitted to the destination, the destination to process the packet and the acknowledgement to be returned to the source. It is not uncommon for this round trip delay to be in the order of several microseconds. Thus, the source is forced to be idle for a prolonged period of time.
To mitigate this performance impact, many protocols permit the transmission of multiple packets without waiting for receipt of an acknowledgement. Each outgoing packet is given a unique identifier, typically a sequence number. At a later time, the destination sends an acknowledgement to the source, identifying the packet by the sequence number. One such protocol implementing this scheme is ASI (Advanced Switching Interconnect).
ASI is an industry standard protocol, based on the PCI Express specification. Advanced Switching (AS) allows for the standardization of today's proprietary based backplanes. Advanced Switching uses the same physical-link and data-link layers as the PCI Express architecture, taking advantage of the tremendously large ecosystem. AS is a multi-point, peer-to-peer switched interconnect standard offering encapsulation of any protocol, multiple messaging mechanisms, QoS including congestion management, extended high availability features and much more. The ASI specification is written, updated and maintained by the ASI SIG (Special Interest Group) and the current version of the specification can be found at www.asi-sig.org/members/Core AS Rev10.pdf, and is hereby incorporated by reference. Similarly, the PCI Express specification is written, updated and maintained by the PCI SIG and the current specification can be found at www.pcisig.org/members/downloads/specifications/pciexpress/pciexpress base 10a.pdf, and is also hereby incorporated by reference.
Many other network protocols, including ASI, define a retry buffer that resides within the source. This retry buffer saves sent packets until they have been acknowledged by the destination. Once an acknowledgement has been received by the source for a specific packet, that packet can then be discarded from the retry buffer. Many protocols, including ASI, also allow a destination to acknowledge multiple transmitted packets simultaneously. For example, assume that packets with sequence numbers 3, 4, 5, 6, 7 and 8 have all been transmitted. An acknowledgement from the destination, indicating a sequence number of 6 would signify that packets with sequence numbers 3, 4, 5 and 6 had all been successfully received. This reduces the number of acknowledgements that need to be transmitted, thus preserving valuable bandwidth. The receipt of this acknowledgement would also cause the source to discard the packets with sequence numbers 3, 4, 5 and 6 from its retry buffer.
FIG. 1 illustrates a typical flowchart for the processing of ACKs and NAKs by the source. Decision Box 10 compares the sequence number received in the acknowledgement (AckNak_Seq_Num) to the last outgoing sequence number (NEXT_TRANSMIT_SEQ-1). If the sequence number specified by the acknowledgement does not correspond to an unacknowledged packet, the incoming acknowledgement is discarded, as shown in Block 50. The sequence number specified by the acknowledgement is also compared to the last received acknowledgement (ACKD_SEQ), as shown in Decision Box 20. If the sequence number differs from this value by too great an amount, then the incoming acknowledgement is discarded, as shown in Block 50. Decision Boxes 10 and 20 serve to guard against erroneously received acknowledgements, and corrupted sequence numbers.
Decision Box 30 compares the sequence number specified by the incoming acknowledgement (AckNak_Seq_Num) to the last received acknowledgement (ACKD_SEQ). If it is different than the previously received sequence number, the source discards from the retry buffer all packets with sequence numbers indicating that they were transmitted earlier than the received sequence number (AckNak_Seq_Num), as shown in Block 60. The source then stores the newly received sequence number as the last received sequence number (ACKD_SEQ), as also shown in Block 60.
Decision Box 40 then determines whether the an acknowledgement (ACK) or negative acknowledgement (NAK) was received. If a NAK was received, the source resends all unacknowledged packets again, as shown in Block 70. Thus, in order for the above process to function properly, the source must store packets since the last acknowledged packet.
This protocol is very effective, especially in scenarios wherein acknowledgements are sent relatively soon after the transmission of the packet. In fact, most protocols specify a time limit within which an acknowledgement must be sent before it is considered a failed transmission. This time limit is sometimes known as the Replay Timer.
Often times, the specified time limit, or Replay Timer, is a function of the underlying communication link. For example, it is common to calculate the timer limit using the following parameters. The packet transmission delay is the actual physical time required for the packet sent by the source to reach the destination. This time is based solely on the length of the communication link. The packet processing delay is the time required for the destination to interpret the packet and generate an acknowledgement in response. The destination send delay is the time required before the acknowledgement can be transmitted. Often, this time is defined as the amount of time required to transmit the longest packet allowed by the protocol. For example, assume that just as the destination is preparing to send the acknowledgement, it begins transmitting (or receiving) a new packet, and that this packet is the longest allowed by the protocol. The destination must wait until this packet has been sent (or received) before it can transmit the acknowledgement. Finally, there is the acknowledgement transmission delay which is the actual physical time required for the acknowledgement to be sent by the destination and received by the source.
To illustrate these parameters, assume a 100 meter link, operating at 2.5 Gb/s, with a maximum packet size of 2 kilobytes. Furthermore, assume that the network protocol has an efficiency of 80%. The packet transmission delay is given by:100 m*5 ns/m=500 nsThe processing delay is based solely on the performance of the destination and therefore cannot be calculated here.The destination send delay is given by:(2 KB*8 bits/byte/0.8)/2.5 Gb/s=8000 nsFinally, the acknowledgement transmission delay is the same as the packet transmission delay, or 500 ns. Thus, the specified time limit or Replay Timer must be greater than 9 microseconds, to account for the packet processing delay at the destination. In the preferred embodiment, there are two timers, the Replay Timer and a second timer in the destination. This second timer, or Ack Latency Timer, specifies the maximum time that the destination may wait before returning an acknowledgement to the sender. This value is preferably less than the value of the Replay Timer. The AS specification suggests recommended time limits for both of these timers, based on maximum payload size and link speed. The specification does allow for multiple packets to be transmitted before an acknowledgement is received.
The size of the retry buffer can then be determined, based on the specified time limit indicated by the Replay Timer. For example, in most protocols, the speed of the communications link is well known. Therefore, the number of bits that can be transmitted during the defined time limit can be defined as:Number of bits transmitted=link speed*time limit.However, not all of the bits transmitted are actual data, which needs to be stored in the retry buffer. Often, there is network information, or overhead, associated with each packet. Therefore, the number of actual data bits which are transmitted during the time limit is given by:Number of data bits=# of bits*protocol efficiency.This number of data bits defines the minimum size of the retry buffer. Referring to the previous example, to support the communications link described above, the retry buffer must be able to store in excess of:2.5 Gb/s*9 μs*0.8=18000 bits, or 2.25 Kbytes.
Even if the protocol specifies a Replay Timer value that is several times greater than the theoretically minimum value to allow multiple outstanding packets, the amount of storage required is feasible in current semiconductor technologies.
However, this implementation is far less feasible when the length of the communications link is significantly increased. Assume that instead of a 100 meter link, the communications link is instead 5 to 10 kilometers, such as is used for MANs (Metro Area Networks). In this scenario, the packet transmission delay and acknowledgement transmission delay increase from 500 ns each to:10 km*5 ns/m=50 microseconds each.Thus, the total specified time limit, or Replay Timer, must be in excess of 108 microseconds. Therefore, the retry buffer must be able to store in excess of:2.5 Gb/s*108 μs*0.8=216000 bits, or 27 Kbytes.If the speed of the link is increased from 2.5 Gb/s to 10 Gb/s, which is also allowed by the AS specification, the buffer requirements grow to in excess of 100 Kbytes.
In addition to the increased amount of storage required for the retry buffer, there is also significant latency in retransmissions. For example, assume that there is a time critical packet to be sent. Just after this time critical packet is sent, a NAK is received for a packet that was transmitted over 100 microseconds ago. Because of this transmission error, all packets that were received after the offending packet will be rejected by the destination and must be resent by the source. In this situation, the entire contents of the retry buffer must be retransmitted, with the time critical packet being the last packet in the retry buffer. Thus, the time critical packet is forced to wait more than 100 microseconds to be transmitted. Such a large delay is unacceptable for a time critical packet.
Thus, in order to utilize the protocol and architecture of AS to achieve long distance interconnections, the issues of buffer size and latency must be addressed. A system and method is needed to retain the AS protocol, while not requiring the large retry buffers and long retry latencies typically associated with long haul protocols.